#ifndef PBVP_CONTOUR_TREE_H
#define PBVP_CONTOUR_TREE_H

#include <vector>
#include <algorithm>

#ifdef NO_HASHMAP
#include <map>
#else
#include <hash_map>
#endif

#include "node.h"

namespace PBVP {
	/**
	* ContourTree -- A class representing the contour tree structure.
	* @note Nodes are always added in ascending order
	*/
	class ContourTree {
	public:
		/**
		* Create an empty contour tree
		*/
		ContourTree();

		///
		virtual ~ContourTree();

		/**
		* Add a node of id n into the contour tree.
		* @param n Node id
		* @param val function of the Node
		*/
		void addNode(int id, float val);

		/**
		 * Add a SuperNode
		 * @param cp
		 */
		void addNode(const CriticalPoint& cp);

		/**
		* Remove a node with id n in the contour tree.
		* @param n Node ID
		*/
		virtual void removeNode(int n);

		/**
		* Add an arc (n, m) into the contour tree.
		* @note Node n and m should already be in the tree.
		* @param x: (n, x) is the edge that cause the addition of this arc.
		*/
		void addArc(int n, int m, int x1 = -1, int x2 = -1);

		/** 
		*  Remove non-critical points to reduce contour tree size
		*/
		virtual void reduce(void);

		/**
		 * 
		 */
		void print(void);

		/**
		* Construct an Augment Contour tree from current contour tree.
		* @note all nodes in the current tree are removed after augmentation.
		*/
		// AugmentedContourTree* augment();

		static ContourTree* mergeTree(ContourTree* p_jtree, ContourTree* p_stree);

		/**
		* Check if a node in the contour tree is leaf.
		* A node is a leaf if it isn't the root and has only one neighbor.
		*/
		bool isLeaf(int n);

		/**
		* Get number of nodes.
		*/
		int numOfNodes() const { return (int)(nodes.size()); }

		/**
		 * 
		 * @param id
		 * 
		 * @return CriticalPoint&
		 */
		CriticalPoint& getCriticalPoint(int id) {
			return nodes[id];
		} 

		/**
		* Get the Node with given id in the contour tree.
		* @return NULL if no node with id n in the tree
		*/
		SuperNode& getNode(int id) {
			return nodes[id];
		}

		/**
		* Get the sorted vector of all critical points in the contour tree
		*/
		std::vector<CriticalPoint>* getSortedPoints() {
			std::vector<CriticalPoint>* pCPVector = new std::vector<CriticalPoint>;

			SuperNodeMap::iterator it = nodes.begin();
			while(it != nodes.end()) {
				pCPVector->push_back((*it).second);
				++it;
			}
			std::sort(pCPVector->begin(), pCPVector->end());
			return pCPVector;
		}

		/**
		* Truncate all vertices lower than x;
		*/
		void truncateLower(float x);

		/**
		* Write the contour tree to a file
		*/
		virtual bool saveFile(const char* fname);

		/**
		* Read contents of a contour tree from a file
		*/
		virtual bool loadFile(const char* fname);

		/*
		*	Set the maximum ID of the critical points
		*/
		void setMaxID(int _id) {
			m_MaxId = _id;
		}
		/**
		 * Get the maximum Id of the critical points
		 * @return int
		 */
		int getMaxID() const {
			return m_MaxId;
		}

	protected:
		/// Leaf Node data structure
		typedef struct LeafNode {
			LeafNode(int _id, unsigned char _type) {
				id = _id;
				type = _type;
			}

			int id;
			unsigned char type;		// 0: join tree, 1: split tree
		} LeafNode;

#ifdef NO_HASHMAP
		typedef std::map<int, SuperNode> SuperNodeMap;
#else
		typedef stdext::hash_map<int, SuperNode> SuperNodeMap;
#endif
		/// SuperNodes in the contour tree
		SuperNodeMap nodes;

		/// The Id of the root node when constructing join and split trees
		int m_MaxId;
	};
}
#endif


